# -*- coding: utf-8 -*-

"""62. 不同路径
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？

示例 1：
输入：m = 3, n = 7
输出：28

示例 2：
输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下

示例 3：
输入：m = 7, n = 3
输出：28

示例 4：
输入：m = 3, n = 3
输出：6

提示：
1 <= m, n <= 100
题目数据保证答案小于等于 2 * 10^9"""

class Solution:
    """
    定义 f(i,j) 为到达点 (i,j) 的不同路径数
    递归基础：
    f(0,x) = 1    # 到达首行每个位置的路径只有一条
    f(x,0) = 1    # 到达首列每个位置的路径只有一条

    f(i,j) = f(i-1, j) + f(i, j-1)      # 从次行次列开始，到达每个位置的路径数为左侧和上侧位置的和

    将递归的计算过程，通过动态规划转换为状态缓存。

    在用代码实现的时候，可以将二维数组压缩为一维，因为计算下一行的时候，只需要上一行，同时可以将计算结果直接更新到这一维，当本行计算结束，这个一维数组中原来保存着上一行的结果，运算后就保存着下一行的结果。
    反正最后也只需要去右下角最后一行最后一列的结果。
    """
    def uniquePaths(self, m: int, n: int) -> int:
        dp = list(range(n))
        i = 0
        while i < m:
            j = 0
            while j < n:
                if i == 0 or j == 0:
                    dp[j] = 1
                else:
                    dp[j] = dp[j-1] + dp[j]
                j += 1
            i += 1
        return dp[n-1]

if __name__ == '__main__':
    print(Solution().uniquePaths(3, 7))
